Viterbi decoders of this type have high error correction capability and are employed in information communication systems such as decoding apparatus and receiving apparatus for use with transmission schemes for satellite communication and mobile communication where errors are more likely to occur.
Viterbi decoding accomplishes decoding through performing a process of finding the difference (branch metric) between received data sequence and expected data sequence, repeating simple processing (ACS) of addition, comparison and selection, and traceback processing of decoded data finally. With this Viterbi decoding, every time coded data corresponding to one input bit is obtained, the distance between signals of the paths of each state at this time is calculated and remaining paths are found.
For example, when the coding scheme is convolutional coding, Viterbi decoding processing is performed as follows.
The convolutional code is generated from the exclusive logical sum of input bit and preceding a fixed number of bits and a prefixed number of preceding bits, and a plurality of coded data is generated in response to one input bit. The number of input bits (information bits) having influence on this coded data is called constraint length K, and the number is equivalent to the number of stages of shift registers used with exclusive logical sums.
The coded data is defined by the state of input bit and (K−1) preceding input bits. These states shift to new states when new input bit is input. However, whether or not a state can be shifted is determined depending on whether the new input is “0” or “1.” The number of states becomes (2K−1) because each of (K−1) bits can be “0” or “1.”
In Viterbi decoding, a received coded data sequence is observed and the most probable state is estimated from all possible states. Therefore, in Viterbi decoding, every time coded data corresponding to one input bit is obtained, the distance between signals (metric) of the paths of each state at the time is calculated, and, among paths that reach the same state, the path having the smaller path is left as a remaining path.
FIG. 1 shows that, in a convolutional encoder with a constraint length K, two paths are expanding respectively, indicating state shift from the state of S[j] and S[j+m/2] at time t−1 of previous time to the state of S[2j] and S[2j+1] at time t. Here, j represents a positive integer number and m represents the number of states.
In FIG. 1, path metric A1 is a sum of the distance between signals (branch metric B1) of expected data sequence and received data sequence that are output when shifting to state S[2j] and path metric PM[j] to state S[j] at previous time.
Likewise, path metric A2 represents a sum of the distance between signals (branch metric B2) of expected data sequence and received data sequence that are output when shifting to state S[2j] and path metric PM[j+m/2] to state S[j+m/2] at previous time.
Thus calculated path metric A1 and A2, which are input to state S[2j], are compared, and the smaller path is selected as a remaining path. Further, the path metric of the selected path is renewed as a path metric until reaching state S[2j] at present time t.
In addition, history of which of path metric A1 and A2 is selected is left as path select signal PS[i] (i=0˜2k−1−1). At this time, when the previous state number of the selected path is smaller than the previous state number of the other, unselected path, PS[i] is 0, or is 1 otherwise.
These processes are performed as many times as the number of times of: the number of states multiplied by traceback length. Further, path select signals of: the number of states multiplied by traceback length; and path metrics of the number of states at final time, are obtained. After that, traceback is performed and coded data is decoded with these information.
Next, the traceback processing will be explained briefly with reference to FIG. 2. FIG. 2 is a trellis diagram showing a history of shifting of each state at the time when number of times of processing of the state number multiplied by length, given that constraint length is “3” and traceback length is “7,” is finished. Numerical values on the line between states represent path select signals when each state is shifting and path described in a solid line is a remaining path.
In the traceback processing, the path metric of each state at the final time is referred to and the state in which path the metric becomes the smallest is selected. However, when known data sequence is attached to input data sequence of coded data as tail bit, the state indicated by this tail bit is uniquely selected (assuming S[00] is selected in this example). Next, the state goes back to the state one time earlier than the path select signal selected at final time. In addition, the path select signal at this time is output as decoded data. Similarly, subsequently, decoded data of traceback length is output following back the states (the path shown in bold line in FIG. 2) at every unit of time based on the path select signal. This processing makes it possible to decode the decoded data sequence (in this case, 1→0→1→1→0→0→0).
By the way, with this Viterbi decoder, the error correction capability improves as the constraint length becomes larger, and the processing amount increases by increasing the constraint length. Therefore, in conventional information communication systems, a coding scheme having a large constraint length is employed when information source which requires high error correction capability is transmitted, and a coding scheme having a short constraint length is employed when information source which tolerates a certain amount of errors is transmitted. However, with schemes like this, in one information communication system, signals that are coded by a plurality of constraint lengths need to be decoded.
On the other hand, when equalization processing of received signal is performed, it is possible to perform equalization processing with higher accuracy by arbitrarily changing the number of coefficients of the estimated transmission path according to the condition of the transmission path. However, in order to perform equalization processing with high accuracy, the Viterbi decoder needs to be versatile and be able to support any arbitrary number of coefficients of the estimated transmission path.
Especially, in the field of mobile communications adopting the Viterbi decoding method, battery is used as a power source to improve the portability of the communication terminal apparatus, and so reducing power consumption is a material requirement.
For this reason, with conventional Viterbi decoders, dedicated hardware has been used to perform routine processing such as the calculation of branch metric or path metric that does not depend on the constraint length or suchlike for reduced power consumption. In addition, software has been used to perform processing whose processing flow is supposed to change according to constraint length such as coding from path select signal or maximum likelihood decision (for example, see Unexamined Japanese Patent Application Publication No. HEI11-74800).
By the way, in the field of mobile communications, there is demand for expansion of continuous call time of the communication terminal apparatus and reduction of battery capacity for improved portability. It is therefore desirable to provide a Viterbi that supports any arbitrary constraint length and any arbitrary number of coefficients of the estimated transmission path in dedicated hardware configuration requiring little power consumption, to realize a communication terminal apparatus requiring little power consumption, such as described above.
However, with conventional Viterbi decoders, as mentioned earlier, software is used for complex processing; therefore, the problem is that it requires large amount of power and is difficult to fulfill the above-mentioned requirement.